////////////////////////////////////////////////////////////////////////////////
// Auteur	: Maxime Vanier et Patrick Losier
// date		: 04/03/2013
//
// description : Implementation de l'algorithme Vorace probabiliste
///////////////////////////////////////////////////////////////////////////////

#include "Algorithmes.h"
#include "BTS.h"
#include "Timer.h"
#include <stdlib.h>
#include <time.h>

const std::string AlgoVorace::ID_VORACE = "algo_vorace_prob";

AlgoVorace::AlgoVorace(bool probabilist)
	: Algo(ID_VORACE)
	, probabilist_(probabilist)
{

}

AlgoVorace::~AlgoVorace()
{

}

int AlgoVorace::execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result)
{
	// On lance l'algo 10 fois et on retient la meilleure solution
	valeurMax_ = 0;
	std::vector<int> bestResult;

	for (int i = 0 ; i < 10 ; i++)
	{
		// Si l'execution est plus longue que le timeout on arrete l'algorithme
		if (time_ > timeout_)
		{
			return -1;
		}

		Timer timer;
		timer.start();

		std::vector<int> resultIt;
		int currentIteration = executeIteration(vBTS, capacite, resultIt);
		if (currentIteration > valeurMax_)
		{
			valeurMax_ = currentIteration;
			bestResult.clear();
			bestResult = resultIt;
		}
		timer.stop();
		time_ += timer.getElapsedTimeInMilliSec();

	}

	// valeur de la solution (-1 si aucune)
	return 0;
}

int AlgoVorace::executeIteration(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result)
{
	result.clear();
	int leftCapacity = capacite;
	int currentValue = 0;
	bool finish = false;

	srand(time(0));
	std::map<int,BTS*> tempMap = vBTS;
	while(!finish || !tempMap.empty())
	{
		BTS* temp = chooseBestLeft(tempMap);
		if (temp)
		{
			if (temp->getNbAbonnes() < leftCapacity)
			{
				result.push_back(temp->getIndex());

				leftCapacity -= temp->getNbAbonnes();
				currentValue += temp->getRevenu();
			}
			tempMap.erase(temp->getIndex());
		}
		else
		{
			finish = true;
		}
	}

	// valeur de la solution (-1 si aucune)
	return currentValue;
}

BTS* AlgoVorace::chooseBestLeft(const std::map<int, BTS*>& vBTS)
{
	// Si on peut fractionner les objets on prend le meilleur ratio, sinon on choisi
	// de facon probabiliste proportionnel au ratio
	if (vBTS.empty())
		return NULL;

	std::map<int, BTS*>::const_iterator itBTS = vBTS.begin();
	if (vBTS.size() == 1)
	{
		return itBTS->second;
	}

	double maxRatio = 0;
	double sumRatio = 0;
	BTS* tempBTS = NULL;	
	for (itBTS ; itBTS != vBTS.end() ; itBTS++)
	{
		double tempRatio = itBTS->second->getRevenuPerCapita();
		sumRatio += tempRatio;

		if (tempRatio > maxRatio)
		{
			maxRatio = tempRatio;
			tempBTS = itBTS->second;
		}
	}

	if (!probabilist_)
	{
		return tempBTS;
	}

	// On trouve le BTS correspondant au nombre tire au hasard
	int intTempRatio = sumRatio;
	int randx = rand();
	int prob = 0;
	if (intTempRatio != 0)
	{
		prob = randx % intTempRatio; // 0 @ sumRatio - 1
	}
	tempBTS = NULL;

	double currentSum = 0;
	itBTS = vBTS.begin();
	for (itBTS ; itBTS != vBTS.end() ; itBTS++)
	{
		double tempRatio = itBTS->second->getRevenuPerCapita();
		currentSum += tempRatio;

		if (currentSum > prob)
		{
			tempBTS = itBTS->second;
			return tempBTS;
		}
	}

	return NULL;
}

